Efficient algorithm for calculating short cycles in Tanner graph based on matrix computation

Loop distribution of Tanner graph affects the BER performance of low-density parity-check codes(LDPC) decoding.To count short cycles in the Tanner graph efficiently,a side by side recursion algorithm based on matrix computation was proposed.Firstly,5 basic graph structures were defined to realize recursive calculate in the implementation process.Compared with previous works,the algorithm provided many methods for counting the same length of cycles.The same result confirmed the correctness of the algorithm.The new algorithm could not only calculate the total number of cycles,but also gave the number each edge participating in fixed-length cycles.Its complexity was proportional to the product of D and square of N,where D was the average degree of variable nodes,and N denoted the code length.For LDPC codes,D was far less than N.For most of the LDPC codes,the calculation for numbers of cycle-length g、g+2、g+4 was only several seconds.     

A distributed command governor based on graph colorability theory

In this paper, a distributed command governor (CG) strategy is introduced that, by the use of graph colorability theory, improves the scalability property and the performance of recently introduced distributed noncooperative sequential CG strategies. The latter are characterized by the fact that only 1 agent at a decision time is allowed to update its command, whereas all the others keep applying their previously computed commands. The scalability of these early CG distributed schemes and their performance are limited because the structure of the constraints is not taken into account in their implementation. Here, by exploiting the idea that agents that are not directly coupled by the constraints can simultaneously update their control actions, the agents in the network are grouped into particular subsets (turns). At each time instant, on the basis of a round‐robin policy, all agents belonging to a turn are allowed to update simultaneously their commands, whereas agents in other turns keep applying their previous commands. Then, a turn‐based distributed CG strategy is proposed and its main properties are analyzed. Graph colorability theory is used to determine the minimal number of turns and to distribute each agent in at least a turn. A novel graph colorability problem that allows one to maximize the frequency at which agents can update their commands is proposed and discussed. A final example is presented to illustrate the effectiveness of the proposed strategy.     

基于二分图的宝鸡公交线路-站点网络建模及分析

复杂网络理论已成为研究交通系统的有效工具。以陕西省宝鸡市的43个公交线路及344个公交站点数据为基础,基于二分图理论,构建了站点-线路公交网络模型,并对该网络的统计性质进行了分析。研究结果表明,网络中的线路节点度分布呈现泊松分布,大部分线路度值集中在平均值附近;而站点节点度分布呈现幂律分布,其中的少数节点高度连接,为网络中的关键枢纽节点。这些高度连接的线路和站点可被筛选为宝鸡市交通网络研究中的重点规划对象。     

Supporting ontology adaptation and versioning based on a graph of relevance

Ontologies recently have become a topic of interest in computer science since they are seen as a semantic support to explicit and enrich data-models as well as to ensure interoperability of data. Moreover, supporting ontology adaptation becomes essential and extremely important, mainly when using ontologies in changing environments. An important issue when dealing with ontology adaptation is the management of several versions. Ontology versioning is a complex and multifaceted problem as it should take into account change management, versions storage and access, consistency issues, etc. The purpose of this paper is to propose an approach and tool for ontology adaptation and versioning. A series of techniques are proposed to ‘safely’ evolve a given ontology and produce a new consistent version. The ontology versions are ordered in a graph according to their relevance. The relevance is computed based on four criteria: conceptualisation, usage frequency, abstraction and completeness. The techniques to carry out the versioning process are implemented in the Consistology tool, which has been developed to assist users in expressing adaptation requirements and managing ontology versions.     

Hierarchical Implicit Shape Modeling

In this paper, a new hierarchical approach for object detection is proposed. Object detection methods based on Implicit Shape Model (ISM) efficiently handle deformable objects, occlusions and clutters. The structure of each object in ISM is defined by a spring like graph. We introduce hierarchical ISM in which structure of each object is defined by a hierarchical star graph. Hierarchical ISM has two layers. In the first layer, a set of local ISMs are used to model object parts. In the second layer, structure of parts with respect to the object center is modeled by global ISM. In the proposed approach, the obtained parts for each object category have high discriminative ability. Therefore, our approach does not require a verification stage. We applied the proposed approach to some datasets and compared the performance of our algorithm to comparable methods. The results show that our method has a superior performance.     

Graph-based Lexicalized Reordering Models for Statistical Machine Translation

Lexicalized reordering models are very important components of phrasebased translation systems.By examining the reordering relationships between adjacent phrases,conventional methods learn these models from the word aligned bilingual corpus,while ignoring the effect of the number of adjacent bilingual phrases.In this paper,we propose a method to take the number of adjacent phrases into account for better estimation of reordering models.Instead of just checking whether there is one phrase adjacent to a given phrase,our method firstly uses a compact structure named reordering graph to represent all phrase segmentations of a parallel sentence,then the effect of the adjacent phrase number can be quantified in a forward-backward fashion,and finally incorporated into the estimation of reordering models.Experimental results on the NIST Chinese-English and WMT French-Spanish data sets show that our approach significantly outperforms the baseline method.     

1∶2000成图比例尺数字航空摄影测量质量控制与保障

通过《太原市1∶2 000成图比例尺数字航空摄影测量》项目实践,以该项目中1∶2 000数字线划图制作为例,结合数据分层详细介绍了数字摄影测量中的质量控制与保障的措施,以供类似测量工作借鉴。     

OPTIMIZATION OF REDUNDANCY IN WATER DISTRIBUTION NETWORKS USING GRAPH THEORETIC PRINCIPLES

An integer goal programming based approach to maximize reliability in water distribution networks is developed. Previous work has shown that graphs which are inherently the most invulnerable to failure have the same number of links incident at each node, i.e. they are regular in degree. The converse of this statement is not true. Regular graphs can contain weaknesses such as bridges, articulation nodes, and even total disconnections. The integer goal programming formulation in this paper is combined with a procedure which recognizes both explicit and implicit articulation points within the water distribution network to ensure that such weaknesses are excluded from the final solution. The integer program component of the approach attempts to maximize regularity within the network. In the goal programming context this is achieved by minimizing the sum of the deviations, at each node, in terms of the number of links incident upon it, from the average number of links incident on a node over the whole network. The integer requirement is imposed to prevent non-integer numbers of links being selected by the model.     

Modeling sleep mode gains in energy-aware networks

Nowadays two main approaches are being pursued to reduce energy consumption of networks: the use of sleep modes in which devices enter a low-power state during inactivity periods, and the adoption of energy proportional mechanisms where the device architecture is designed to make energy consumption proportional to the actual load. Common to all the proposals is the evaluation of energy saving performance by means of simulation or experimental evidence, which typically consider a limited set of benchmarking scenarios.     

A novel intelligent verification platform based on a structured analysis model

An intelligent verification platform based on a structured analysis model is presented.Using an abstract model mechanism with specific signal interfaces for user callback,the unified structured analysis data,shared by the electronic system level design,functional verification,and performance evaluation,enables efficient management review,auto-generation of code,and modeling in the transaction level.We introduce the class tree,flow parameter diagram,structured flow chart,and event-driven finite state machine as structured analysis models.As a sand table to carry maps from different perspectives and levels via an engine,this highly reusable platform provides the mapping topology to search for unintended consequences and the graph theory for comprehensive coverage and smart test cases.Experimental results show that the engine generates efficient test sequences,with a sharp increase in coverage for the same vector count compared with a random test.